{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Submatrices With All Ones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #dynamic-programming #matrix #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #动态规划 #矩阵 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSubmat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计全 1 子矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的二进制矩阵&nbsp;<code>mat</code>&nbsp;，请你返回有多少个&nbsp;<strong>子矩形</strong>&nbsp;的元素全部都是 1 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/10/27/ones1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,0,1],[1,1,0],[1,1,0]]\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：\n",
    "</strong>有 <strong>6</strong>&nbsp;个 1x1 的矩形。\n",
    "有 <strong>2</strong> 个 1x2 的矩形。\n",
    "有 <strong>3</strong> 个 2x1 的矩形。\n",
    "有 <strong>1</strong> 个 2x2 的矩形。\n",
    "有 <strong>1</strong> 个 3x1 的矩形。\n",
    "矩形数目总共 = 6 + 2 + 3 + 1 + 1 = <strong>13</strong>&nbsp;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/10/27/ones2-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]\n",
    "<strong>输出：</strong>24\n",
    "<strong>解释：</strong>\n",
    "有 <strong>8</strong> 个 1x1 的子矩形。\n",
    "有 <strong>5</strong> 个 1x2 的子矩形。\n",
    "有 <strong>2</strong> 个 1x3 的子矩形。\n",
    "有 <strong>4</strong> 个 2x1 的子矩形。\n",
    "有 <strong>2</strong> 个 2x2 的子矩形。\n",
    "有 <strong>2</strong> 个 3x1 的子矩形。\n",
    "有 <strong>1</strong> 个 3x2 的子矩形。\n",
    "矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = <strong>24</strong><strong> 。</strong>\n",
    "\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 150</code></li>\n",
    "\t<li><code>mat[i][j]</code>&nbsp;仅包含&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-submatrices-with-all-ones](https://leetcode.cn/problems/count-submatrices-with-all-ones/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-submatrices-with-all-ones](https://leetcode.cn/problems/count-submatrices-with-all-ones/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,1],[1,1,0],[1,1,0]]', '[[0,1,1,0],[0,1,1,1],[1,1,1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        # 对每一行采用单调栈，同时也采用每一行计数\n",
    "        # 主要是想办法找出使该点作为矩形右下角后。求矩形的最左侧\n",
    "        m, n, ans = len(mat), len(mat[0]), 0\n",
    "        his = [0] * (n + 1) # 每一行统计时，记录该位置上已经有多少连续1\n",
    "        for i in range(m):\n",
    "            stack, dp = [-1], [0] * (n + 1)\n",
    "            for j in range(n):\n",
    "                his[j] = 0 if mat[i][j] == 0 else his[j] + 1\n",
    "                while his[j] < his[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                dp[j] = dp[stack[-1]] + his[j] * (j - stack[-1]) # Important!!\n",
    "                stack.append(j)\n",
    "            # print(dp)\n",
    "            ans += sum(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    cur += 1\n",
    "                    mat[i][j] = cur\n",
    "                else:\n",
    "                    cur = 0\n",
    "        \n",
    "        for col in zip(*mat):\n",
    "            total = 0\n",
    "            st = []\n",
    "            for x in col:\n",
    "                h = 1\n",
    "                if x:\n",
    "                    while st and x < st[-1][0]:\n",
    "                        total += (x - st[-1][0]) * st[-1][1]\n",
    "                        h += st[-1][1]\n",
    "                        st.pop()\n",
    "                    st.append((x, h))\n",
    "                    total += x\n",
    "                    ans += total\n",
    "                else:\n",
    "                    st = []\n",
    "                    total = 0\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m,n,res=len(mat),len(mat[0]),0\n",
    "        histogram=[0]*(n+1)\n",
    "        for i in range(m):\n",
    "            stack,dp=[-1],[0]*(n+1)\n",
    "            for j in range(n):\n",
    "                histogram[j]=0 if mat[i][j]==0 else histogram[j]+1\n",
    "                while len(stack)>1 and histogram[j]<histogram[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                dp[j]=dp[stack[-1]]+histogram[j]*(j-stack[-1]) # Important!! 动态规划\n",
    "                stack.append(j)\n",
    "            res+=sum(dp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        stack = []\n",
    "        n = len(mat[0])\n",
    "        heights = [0] * n\n",
    "        ans = 0\n",
    "        for m in mat:\n",
    "            for i in range(n):\n",
    "                heights[i] = 0 if m[i] == 0 else heights[i] + 1\n",
    "                while stack and heights[i] <= heights[stack[-1]]:\n",
    "                    cur = stack.pop()\n",
    "                    left = stack[-1] if stack else -1\n",
    "                    right = i\n",
    "                    le = right - left - 1\n",
    "                    quantity = (heights[cur]-max(heights[left] if stack else 0, heights[right])) * le *(le +1)//2\n",
    "                    ans += quantity\n",
    "                stack.append(i)\n",
    "            while stack:\n",
    "                    cur = stack.pop()\n",
    "                    left = stack[-1] if stack else -1\n",
    "                    right = n\n",
    "                    le = right - left - 1\n",
    "                    quantity = (heights[cur]- (heights[left] if stack else 0)) * le *(le +1)//2\n",
    "                    ans += quantity\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        a = [0] * m \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]: a[j] += 1\n",
    "                else: a[j] = 0\n",
    "            \n",
    "            for j in range(m):\n",
    "                v = a[j]\n",
    "                for k in range(j, -1, -1):\n",
    "                    if a[k] == 0: break\n",
    "                    v = min(v, a[k])\n",
    "                    res += v \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        a = [0] * m \n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]: a[j] += 1\n",
    "                else: a[j] = 0\n",
    "\n",
    "            total = 0\n",
    "            st = []\n",
    "            for j in range(m):\n",
    "                h = 0\n",
    "                while st and st[-1][0] > a[j]:\n",
    "                    total -= (st[-1][0] - a[j]) * st[-1][1]\n",
    "                    h += st[-1][1]\n",
    "                    st.pop()\n",
    "                total += a[j]\n",
    "                res += total \n",
    "                st.append((a[j], h+1))\n",
    "            # print(res)\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m,n,res=len(mat),len(mat[0]),0\n",
    "        histogram=[0]*(n+1)\n",
    "        for i in range(m):\n",
    "            stack,dp=[-1],[0]*(n+1)\n",
    "            for j in range(n):\n",
    "                histogram[j]=0 if mat[i][j]==0 else histogram[j]+1\n",
    "                while histogram[j]<histogram[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                dp[j]=dp[stack[-1]]+histogram[j]*(j-stack[-1]) # Important!! 动态规划\n",
    "                stack.append(j)\n",
    "            res+=sum(dp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        dp=[[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j==0:\n",
    "                    dp[i][j]=mat[i][j]\n",
    "                else:\n",
    "                    dp[i][j]=dp[i][j-1]+1 if mat[i][j] else 0\n",
    "\n",
    "\n",
    "        ans=0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                minn=inf\n",
    "\n",
    "                for k in range(i,-1,-1):\n",
    "                    minn=min(minn,dp[k][j])\n",
    "                    ans+=minn\n",
    "                    if minn==0:break\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        ans = 0\n",
    "        cnt = [0] * n\n",
    "        for j in range(m):\n",
    "            for i in range(n):\n",
    "                if j == 0:\n",
    "                    cnt[i] = 1 if mat[i][j] == 1 else 0\n",
    "                else:\n",
    "                    cnt[i] = cnt[i] + 1 if mat[i][j] == 1 else 0\n",
    "                if mat[i][j] == 0:\n",
    "                    continue\n",
    "                mn = cnt[i]\n",
    "                for k in range(i, -1, -1):\n",
    "                    mn = min(mn, cnt[k])\n",
    "                    ans += mn\n",
    "                    if cnt[k] == 0:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        '''\n",
    "            思路：从上往下以每一行作为 底，来计算。每一次都调用单调递减栈。\n",
    "                维护单调性时，进行结算，比如弹出 pos位置，\n",
    "                left低   pos高   i低\n",
    "                这种情况，pos就是需要结算的，表示 以height[pos]作为高时，有多少个子矩阵\n",
    "        '''\n",
    "        def calc(height: List[int]) -> int:\n",
    "            n = len(height)\n",
    "            stack = [] # 单调递减栈\n",
    "            ans = 0\n",
    "            for i, x in enumerate(height):\n",
    "                while stack and x <= height[stack[-1]]:\n",
    "                    pos = stack.pop()\n",
    "                    left = stack[-1] if stack else -1\n",
    "                    left_height = 0 if left == -1 else height[left]\n",
    "                    down = height[pos] - max(left_height, x)\n",
    "                    ans += down * get(i - left - 1)\n",
    "                stack.append(i)\n",
    "            \n",
    "            while stack:\n",
    "                pos = stack.pop()\n",
    "                left = stack[-1] if stack else -1\n",
    "                left_height = 0 if left == -1 else height[left]\n",
    "                down = height[pos] - left_height\n",
    "                ans += down * get(n - left - 1)\n",
    "            return ans\n",
    "        \n",
    "        def get(x: int) -> int:\n",
    "            return (1 + x) * x // 2\n",
    "        ans = 0 \n",
    "        height = [0] * len(mat[0])\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                height[j] = 0 if mat[i][j] == 0 else height[j] + 1\n",
    "            ans += calc(height)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "        res=0\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if mat[i-1][j-1]==1:\n",
    "                    dp[i][j]=dp[i][j-1]+1\n",
    "                mmax=dp[i][j]\n",
    "                for k in range(i,-1,-1):\n",
    "                    mmax=min(mmax,dp[k][j])\n",
    "                    res+=mmax\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    f[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    f[i][j] = (f[i][j - 1] + mat[i][j]) * mat[i][j]\n",
    "        res = 0\n",
    "        for j in range(n):\n",
    "            st, cur = [], 0\n",
    "            for i in range(m):\n",
    "                h = 1\n",
    "                while st and st[-1][0] >= f[i][j]:\n",
    "                    tw, th = st.pop()\n",
    "                    cur -= th * (tw - f[i][j])\n",
    "                    h += th\n",
    "                cur += f[i][j]\n",
    "                res += cur\n",
    "                st.append((f[i][j], h))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            # 计数\n",
    "            for j in range(i, m):\n",
    "                cnt = 0\n",
    "                for k in range(n):\n",
    "                    if mat[j][k]:\n",
    "                        cnt = 1 if k == 0 else cnt + 1\n",
    "                        ans += cnt\n",
    "                    else:\n",
    "                        cnt = 0\n",
    "            # 压缩\n",
    "            for j in range(m - 1, i, - 1):\n",
    "                for k in range(n):\n",
    "                    mat[j][k] &= mat[j - 1][k]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MAXM = 151\n",
    "\n",
    "    def numSubmat(self, mat):\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        ans = 0\n",
    "        height = [0] * m\n",
    "        stack = []\n",
    "        r = 0\n",
    "\n",
    "        def count_from_bottom():\n",
    "            nonlocal r\n",
    "            nonlocal ans\n",
    "            r = 0\n",
    "            for i in range(m):\n",
    "                left = stack[-1] if stack else -1\n",
    "                while stack and height[stack[-1]] >= height[i]:\n",
    "                    cur = stack.pop()\n",
    "                    left = stack[-1] if stack else -1\n",
    "                    if height[cur] > height[i]:\n",
    "                        len_val = i - left - 1\n",
    "                        bottom = max(0 if left == -1 else height[left], height[i])\n",
    "                        ans += (height[cur] - bottom) * len_val * (len_val + 1) // 2\n",
    "                stack.append(i)\n",
    "                r += 1\n",
    "\n",
    "            while stack:\n",
    "                cur = stack.pop()\n",
    "                left = stack[-1] if stack else -1\n",
    "                len_val = m - left - 1\n",
    "                down = 0 if left == -1 else height[left]\n",
    "                ans += (height[cur] - down) * len_val * (len_val + 1) // 2\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                height[j] = 0 if mat[i][j] == 0 else height[j] + 1\n",
    "            count_from_bottom()\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 示例用法\n",
    "solution = Solution()\n",
    "mat = [\n",
    "    [1, 0, 1],\n",
    "    [1, 1, 0],\n",
    "    [1, 1, 0]\n",
    "]\n",
    "result = solution.numSubmat(mat)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            arr = []\n",
    "            for j in range(m):\n",
    "                num = 0\n",
    "                k = i\n",
    "                while k >= 0 and mat[k][j] == 1:\n",
    "                    num += 1\n",
    "                    k -= 1\n",
    "                arr.append(num)\n",
    "            \n",
    "            l = []\n",
    "            left = [-1]*m\n",
    "            right = [m]*m\n",
    "            # print(arr)\n",
    "            for i in range(m):\n",
    "                while l and arr[l[-1]]>arr[i]:\n",
    "                    x = l.pop()\n",
    "                    right[x] = i\n",
    "                    if l:\n",
    "                        left[x] = l[-1]\n",
    "                l.append(i)\n",
    "            while l:\n",
    "                x = l.pop()\n",
    "                if l:\n",
    "                    left[x] = l[-1]\n",
    "            # for i in range(m-1,-1,-1):\n",
    "            #     if right[i] != m and arr[right[i]] == arr[i]:\n",
    "            #         right[i] = right[right[i]]\n",
    "            # print(left)\n",
    "            # print(right)\n",
    "            for i in range(m):\n",
    "                if arr[i]:\n",
    "                    if left[i] == -1:\n",
    "                        lv = 0\n",
    "                    else:\n",
    "                        lv = arr[left[i]]\n",
    "                    if right[i] == m:\n",
    "                        rv = 0\n",
    "                    else:\n",
    "                        rv = arr[right[i]]\n",
    "                    ans += (right[i]- left[i])*(right[i]- left[i]-1)//2*(arr[i] - max(lv,rv) )\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        # 1 <= m, n <= 150 \n",
    "        # 动态规划预处理一下就行了 3.75 * 10^6\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[mat[i][j] for j in range(n)] for i in range(m)]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    dp[i][j] = dp[i+1][j] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                max_len = inf\n",
    "                for k in range(j, n):\n",
    "                    max_len = min(max_len, dp[i][k])\n",
    "                    if max_len == 0:\n",
    "                        break\n",
    "                    ans += max_len\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        n = len(mat[0])\n",
    "        heights = [0]*n\n",
    "        for line in mat:\n",
    "            heights = [0 if line[i] == 0 else heights[i]+1 for i in range(n)]\n",
    "            st = [(-1,0)]\n",
    "            for i,x in enumerate(heights):\n",
    "                while st[-1][1] > x: st.pop()\n",
    "                ans += x*(i-st[-1][0])\n",
    "                for k in range(len(st)-1,0,-1):\n",
    "                    ans += st[k][1] * (st[k][0]-st[k-1][0])\n",
    "                st.append((i,x))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        arr = [0 for _ in range(m)]\n",
    "        stack = [0 for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    arr[j] = 0\n",
    "                else:\n",
    "                    arr[j] += 1\n",
    "            r = 0\n",
    "            for k in range(m):\n",
    "                while r > 0 and arr[k] <= arr[stack[r-1]]:\n",
    "                    r -= 1\n",
    "                    cur = stack[r]\n",
    "                    if arr[k] < arr[cur]:\n",
    "                        if r > 0:\n",
    "                            left = stack[r-1]\n",
    "                            bottom = max(arr[left], arr[k])\n",
    "                        else:\n",
    "                            left = -1\n",
    "                            bottom = max(0, arr[k])\n",
    "                        lens = k - left - 1\n",
    "                        ans += (arr[cur] - bottom) * lens * (lens+1) // 2\n",
    "                stack[r] = k\n",
    "                r += 1\n",
    "            while r > 0:\n",
    "                r -= 1\n",
    "                cur = stack[r]\n",
    "                if r > 0:\n",
    "                    left = stack[r-1]\n",
    "                    down = arr[left]\n",
    "                else:\n",
    "                    left = -1\n",
    "                    down = 0\n",
    "                lens = m - left - 1\n",
    "                ans += (arr[cur] - down) * lens * (lens+1) // 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, a: List[List[int]]) -> int:\n",
    "        m = len(a)\n",
    "        n = len(a[0])\n",
    "        def check(x):\n",
    "            ans = 0\n",
    "            s = []\n",
    "            dic = {j:n for j in range(n)}\n",
    "            dp = {n:0}\n",
    "            for j in range(n):\n",
    "                while s and (x[j] < x[s[-1]]):\n",
    "                    t = s.pop()\n",
    "                    dic[t] = j \n",
    "                s.append(j)\n",
    "            for j in range(n)[::-1]:\n",
    "                r = dic[j]\n",
    "                dp[j] = dp[r] + (r-j)*x[j] \n",
    "            return sum(dp.values())\n",
    "        st = [0]*n \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if a[i][j]==1:\n",
    "                    st[j] += 1\n",
    "                else:\n",
    "                    st[j] = 0 \n",
    "            ans += check(st)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "\n",
    "        dp = mat.copy()\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j != 0 and mat[i][j] == 1:\n",
    "                    dp[i][j] = dp[i][j-1] + 1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if dp[i][j] == 0:\n",
    "                    continue\n",
    "                col = dp[i][j]\n",
    "                ans += col\n",
    "                # 第 k 行到第 i 行「每一行第 j 列向左延伸连续 1 的个数\n",
    "                for k in range(i-1,-1,-1):\n",
    "                    if dp[k][j] == 0:\n",
    "                        break\n",
    "                    col = min(col,dp[k][j])\n",
    "                    ans += col\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: list[list[int]]) -> int:\n",
    "        heights = [0 for i in range(len(mat[0]))]\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        for i in range(len(mat)):\n",
    "            queue = []\n",
    "            dp = [0 for i in range(len(heights))]\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] == 0:\n",
    "                    heights[j] = 0\n",
    "                    queue = [j]\n",
    "                    continue\n",
    "                heights[j] = heights[j] + 1\n",
    "                while queue and heights[queue[-1]] >= heights[j]:\n",
    "                    queue.pop()\n",
    "\n",
    "                start_index = queue[-1] if queue else -1\n",
    "                dp[j] = (j - start_index) * heights[j] + (dp[start_index] if start_index > -1 else 0)\n",
    "                ans += dp[j]\n",
    "                queue.append(j)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = row[i][j - 1] + 1 if mat[i][j] else 0\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    res += col\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        if not mat or not mat[0]: return 0\n",
    "        \n",
    "        rows, cols = len(mat), len(mat[0])\n",
    "        dp = [[0] * cols for _ in range(rows)]  # DP 初始化\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if mat[i][j]:\n",
    "                    dp[i][j] = ((dp[i][j-1] + 1) if j > 0 else 1)\n",
    "                    mmin = float('inf')\n",
    "                    for k in range(i, -1, -1):  # 从i开始遍历,到0结束, 计算能组成的矩阵个数\n",
    "                        mmin = min(mmin, dp[k][j])\n",
    "                        ans += mmin\n",
    "                        \n",
    "                        # 提前结束循环\n",
    "                        if mmin == 0: \n",
    "                            break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "            m,n,res=len(mat),len(mat[0]),0\n",
    "            histogram=[0]*(n+1)\n",
    "            for i in range(m):\n",
    "                stack,dp=[-1],[0]*(n+1)\n",
    "                for j in range(n):\n",
    "                    histogram[j]=0 if mat[i][j]==0 else histogram[j]+1\n",
    "                    while histogram[j]<histogram[stack[-1]]:\n",
    "                        stack.pop()\n",
    "                    dp[j]=dp[stack[-1]]+histogram[j]*(j-stack[-1]) # Important!!\n",
    "                    stack.append(j)\n",
    "                res+=sum(dp)\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        height = [0] * n + [-1]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    height[j] += 1\n",
    "                else:\n",
    "                    height[j] = 0\n",
    "            stack = [-1]\n",
    "            for r, h in enumerate(height):\n",
    "                while len(stack) > 1 and height[stack[-1]] >= h:\n",
    "                    cur = stack.pop()\n",
    "                    length = r - stack[-1] - 1\n",
    "                    width = height[cur] - max(h if h != -1 else 0, height[stack[-1]] if stack[-1] != -1 else 0)\n",
    "                    ans += length * (length + 1) // 2 * width\n",
    "                stack.append(r)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        if not mat or not mat[0]:\n",
    "            return 0\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        pre_cal = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        for j in range(m):\n",
    "            pre_cal[0][j] = mat[0][j]\n",
    "        for i in range(1,n):\n",
    "            for j in range(m):\n",
    "                pre_cal[i][j] = 0 if mat[i][j] == 0 else pre_cal[i-1][j] + 1\n",
    "        #print(\"pre_cal \", pre_cal)\n",
    "        def getOneSum(arr):\n",
    "            n = len(arr)\n",
    "            new_h = [-1 for _ in range(n+2)]\n",
    "            for i in range(1,n+1):\n",
    "                new_h[i] = arr[i-1]\n",
    "            #print(\"new_h\", new_h)\n",
    "            stack = []\n",
    "            area = 0\n",
    "            for r in range(n+2):\n",
    "                while stack and new_h[stack[-1]] > new_h[r]:\n",
    "                    p = stack.pop()\n",
    "                    l = -1 if not stack else stack[-1]\n",
    "                    w = new_h[p] * (r-p) * (p-l)\n",
    "                    #print(new_h[p], l, \"-->\", r)\n",
    "                    if w > 0:\n",
    "                        area += w \n",
    "                stack.append(r)\n",
    "            return area\n",
    "        ans = 0\n",
    "        for t in pre_cal:\n",
    "            ans += getOneSum(t)\n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        # 二维dp\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        dp = [[0] * (n) for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    dp[i][j] = dp[i][j-1] + 1\n",
    "                    mi = dp[i][j]\n",
    "                    for k in range(i,-1,-1):\n",
    "                        mi = min(mi,dp[k][j])\n",
    "                        ans += mi\n",
    "                        if mi == 0:\n",
    "                            break\n",
    "        return ans \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    if mat[i][j] == 1:\n",
    "                        row[i][j] = row[i][j - 1] + 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "\n",
    "                    res += col\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        def calc(heights):\n",
    "            stk=[]\n",
    "            pre,suf=[-1]*len(heights),[len(heights)]*len(heights)\n",
    "            for i in range(len(heights)):\n",
    "                while stk and heights[i]<heights[stk[-1]]:\n",
    "                    suf[stk.pop()]=i\n",
    "                if stk: pre[i]=stk[-1]\n",
    "                stk.append(i)\n",
    "            return sum(heights[i]*(suf[i]-i)*(i-pre[i]) for i in range(len(heights)))\n",
    "        \n",
    "        res=0\n",
    "        heights=[0]*len(mat[0])\n",
    "        for n in mat:\n",
    "            for i in range(len(n)):\n",
    "                heights[i]=heights[i]+1 if n[i] else 0\n",
    "            res+=calc(heights)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        def maxNums(heights):\n",
    "            '''获取每一行子矩形数量'''\n",
    "            n = len(heights)\n",
    "            stack = []\n",
    "            ans = 0\n",
    "\n",
    "            for i in range(n):\n",
    "                while stack and heights[stack[-1]] >= heights[i]:\n",
    "                    up = heights[stack.pop()]\n",
    "                    if up > heights[i]:\n",
    "                        w = i if not stack else i - stack[-1] - 1\n",
    "                        down = max(0 if not stack else heights[stack[-1]], heights[i])\n",
    "                        ans += (up - down) * (w * (w + 1) >> 1)\n",
    "                stack.append(i)\n",
    "            while stack:\n",
    "                up = heights[stack.pop()]\n",
    "                w = n if not stack else n - stack[-1] - 1\n",
    "                down = 0 if not stack else heights[stack[-1]]\n",
    "                ans += (up - down) * (w * (w + 1) >> 1)\n",
    "\n",
    "            return ans\n",
    "\n",
    "\n",
    "        row, col = len(mat), len(mat[0])\n",
    "        heights = [0] * col\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if mat[i][j] == 1:\n",
    "                    heights[j] += 1\n",
    "                else:\n",
    "                    heights[j] = 0\n",
    "            res += maxNums(heights)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n, res = len(mat), len(mat[0]), 0\n",
    "        histogram = [0] * (n+1)\n",
    "        for i in range(m):\n",
    "            st, dp = [-1], [0] * (n+1)\n",
    "            for j in range(n):\n",
    "                histogram[j] = 0 if mat[i][j] == 0 else histogram[j]+1\n",
    "                while len(st) > 1 and histogram[j] < histogram[st[-1]]:\n",
    "                    st.pop()\n",
    "                dp[j] = dp[st[-1]] + histogram[j] * (j - st[-1])\n",
    "                st.append(j)\n",
    "            res += sum(dp)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j-1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            q = list()\n",
    "            total = 0\n",
    "            for i in range(m):\n",
    "                h = 1\n",
    "                # 栈中的元素比当前大，需要pop掉大值\n",
    "                while q and  q[-1][0] > row[i][j]:\n",
    "                    total -= q[-1][1] * (q[-1][0] - row[i][j])\n",
    "                    h += q[-1][1]\n",
    "                    q.pop()\n",
    "                total += row[i][j]\n",
    "                ans += total\n",
    "                q.append((row[i][j], h))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        pre = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    p = j + 1\n",
    "                    temp = 1\n",
    "                    while p < n and mat[i][p] == 1:\n",
    "                        p += 1\n",
    "                        temp += 1\n",
    "                    pre[i][j] = temp\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    p = i + 1\n",
    "                    ans += pre[i][j]\n",
    "                    temp = pre[i][j]\n",
    "                    while p < m and mat[p][j] == 1:\n",
    "                        temp = min(temp, pre[p][j])\n",
    "                        ans += temp\n",
    "                        p += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        \n",
    "        row = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(m):\n",
    "            Q = list()\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                height = 1\n",
    "                while Q and Q[-1][0] > row[i][j]:\n",
    "                    # 弹出的时候要减去多于的答案\n",
    "                    total -= Q[-1][1] * (Q[-1][0] - row[i][j])\n",
    "                    height += Q[-1][1]\n",
    "                    Q.pop()\n",
    "                total += row[i][j]\n",
    "                ans += total\n",
    "                Q.append((row[i][j], height))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        row = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                row[i][j] = mat[i][j] if j == 0 else (row[i][j-1] + 1) * mat[i][j]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    ans += col\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        res=0\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if mat[i-1][j-1]==1:\n",
    "                    dp[i][j]=max(dp[i][j],dp[i][j-1]+1)\n",
    "                mmin=dp[i][j]\n",
    "                for k in range(i,-1,-1):\n",
    "                    mmin=min(mmin,dp[k][j])\n",
    "                    res+=mmin\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j-1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            q = list()\n",
    "            total = 0\n",
    "            for i in range(m):\n",
    "                h = 1\n",
    "                while q and q[-1][0] > row[i][j]:\n",
    "                    pw, ph = q.pop()\n",
    "                    total -= (pw - row[i][j]) * ph\n",
    "                    h += ph\n",
    "                total += row[i][j]\n",
    "                ans += total\n",
    "                q.append((row[i][j], h))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        \n",
    "        row = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    ans += col\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        \n",
    "        row = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(m):\n",
    "            st = [-1]\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                while len(st) > 1 and row[i][j] <= row[st[-1]][j]:\n",
    "                    x = st.pop()\n",
    "                    total -= (x - st[-1]) * row[x][j]\n",
    "                total += (i - st[-1]) * row[i][j]\n",
    "                st.append(i)\n",
    "                # print(row[i][j], total)\n",
    "                ans += total\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "\n",
    "        dp = mat.copy()\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j != 0 and mat[i][j] == 1:\n",
    "                    dp[i][j] = dp[i][j-1] + 1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if dp[i][j] == 0:\n",
    "                    continue\n",
    "                col = dp[i][j]\n",
    "                # ans += col\n",
    "                # 第 k 行到第 i 行「每一行第 j 列向左延伸连续 1 的个数\n",
    "                for k in range(i,-1,-1):\n",
    "                    if dp[k][j] == 0:\n",
    "                        break\n",
    "                    col = min(col,dp[k][j])\n",
    "                    ans += col\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: list[list[int]]) -> int:\n",
    "        heights = [0 for i in range(len(mat[0]))]\n",
    "        ans = 0\n",
    "\n",
    "        cur_len = 0\n",
    "\n",
    "        for i in range(len(heights)):\n",
    "            if mat[0][i]:\n",
    "                heights[i] = int(mat[0][i] == 1)\n",
    "                cur_len = cur_len + 1\n",
    "                ans += cur_len\n",
    "            else:\n",
    "                heights[i] = 0\n",
    "                cur_len = 0\n",
    "\n",
    "        for i in range(1, len(mat)):\n",
    "            queue = []\n",
    "            dp = [0 for i in range(len(heights))]\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] == 0:\n",
    "                    heights[j] = 0\n",
    "                    queue = [j]\n",
    "                    continue\n",
    "                heights[j] = heights[j] + 1\n",
    "                while queue and heights[queue[-1]] >= heights[j]:\n",
    "                    queue.pop()\n",
    "\n",
    "                start_index = queue[-1] if queue else -1\n",
    "                dp[j] = (j - start_index) * heights[j] + (dp[start_index] if start_index > -1 else 0)\n",
    "                ans += dp[j]\n",
    "                queue.append(j)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        # 1 <= m, n <= 150 \n",
    "        # 动态规划预处理一下就行了 3.75 * 10^6\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[mat[i][j] for j in range(n)] for i in range(m)]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    dp[i][j] = dp[i+1][j] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                max_len = inf\n",
    "                for k in range(j, n):\n",
    "                    max_len = min(max_len, dp[i][k])\n",
    "                    if max_len == 0:\n",
    "                        break\n",
    "                    ans += max_len\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j-1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            q = list()\n",
    "            total = 0\n",
    "            for i in range(m):\n",
    "                h = 1\n",
    "                while q and q[-1][0] > row[i][j]:\n",
    "                    total -= q[-1][1] * (q[-1][0] - row[i][j])\n",
    "                    h += q[-1][1]\n",
    "                    q.pop()\n",
    "                total += row[i][j]\n",
    "                ans += total\n",
    "                q.append((row[i][j], h))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j-1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    ans += col\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        # 核心思想：枚举矩阵的右下角，然后看这个矩阵有多少个子矩阵全部都是1\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        # 预处理\n",
    "        row = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j-1]+1\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cnt = row[i][j]\n",
    "                for k in range(i,-1,-1):\n",
    "                    cnt = min(row[k][j],cnt)\n",
    "                    if cnt == 0:\n",
    "                        break\n",
    "                    ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        dp = [[0]*m for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]+1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                col = dp[i][j]\n",
    "                ans += col\n",
    "                for k in range(i-1, -1, -1):\n",
    "                    col = min(col, dp[k][j])\n",
    "                    ans += col\n",
    "                    if col == 0:\n",
    "                        break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        h = len(mat)\n",
    "        w = len(mat[0])\n",
    "\n",
    "        dp = [[0]*w for _ in range(h)]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if mat[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = 1 + dp[i][j-1] if j > 0 else mat[i][j]\n",
    "\n",
    "                min_len = dp[i][j]\n",
    "                res += min_len\n",
    "                for k in range(i-1, -1, -1):\n",
    "                    min_len = min(min_len, dp[k][j])\n",
    "                    res += min_len\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        if not mat or not mat[0]: return 0\n",
    "        \n",
    "        rows, cols = len(mat), len(mat[0])\n",
    "        dp = [[0] * cols for _ in range(rows)]  # DP 初始化\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if mat[i][j]:\n",
    "                    dp[i][j] = ((dp[i][j-1] + 1) if j > 0 else 1)\n",
    "                    mmin = float('inf')\n",
    "                    for k in range(i, -1, -1):  # 从i开始遍历,到0结束, 计算能组成的矩阵个数\n",
    "                        mmin = min(mmin, dp[k][j])\n",
    "                        ans += mmin\n",
    "                        \n",
    "                        # 提前结束循环\n",
    "                        if mmin == 0: \n",
    "                            break\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j-1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # k从i的位置向上找\n",
    "                cnt = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    cnt = min(cnt, row[k][j])\n",
    "                    ans += cnt\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        row = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j-1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    ans += col\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    f[i][j] = (f[i][j-1] + 1) if j > 0 else 1\n",
    "                    mx = f[i][j]\n",
    "                    for k in range(i, -1, -1):\n",
    "                        if f[k][j] == 0: break\n",
    "                        mx = min(mx, f[k][j]) \n",
    "                        ans += mx\n",
    "                        if mx == 0:\n",
    "                            break\n",
    "                # print(f'{ans, i, j}')\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, M: List[List[int]]) -> int:\n",
    "        m, n = len(M), len(M[0])\n",
    "        res = 0\n",
    "        H = [0] * n\n",
    "        for i in range(m):\n",
    "            stk, dp = [], []\n",
    "            for j in range(n):\n",
    "                if M[i][j]: H[j] += 1\n",
    "                else: H[j] = 0\n",
    "                while stk and H[stk[-1]] >= H [j]:\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    v = (j - stk[-1]) * H[j] + dp[stk[-1]]\n",
    "                else:\n",
    "                    v = (j + 1) * H[j]\n",
    "                dp.append(v)\n",
    "                stk.append(j)\n",
    "                res += v\n",
    "            print(i, dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        ans=0\n",
    "        dp=[[0 for i in range(n+1)]for i in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if mat[i-1][j-1]:\n",
    "                    dp[i][j]=dp[i][j-1]+1\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if not mat[i-1][j-1]:\n",
    "                    continue\n",
    "                x=dp[i][j]\n",
    "                for k in range(i,0,-1):\n",
    "                    if dp[k][j]==0:\n",
    "                        break\n",
    "                    if dp[k][j]<x:\n",
    "                        x=dp[k][j]\n",
    "                        ans+=x\n",
    "                    else:\n",
    "                        ans+=x\n",
    "        return ans\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        def calc(heights):\n",
    "            stk=[]\n",
    "            pre,suf=[-1]*len(heights),[len(heights)]*len(heights)\n",
    "            for i in range(len(heights)):\n",
    "                while stk and heights[i]<=heights[stk[-1]]:\n",
    "                    suf[stk.pop()]=i\n",
    "                if stk: pre[i]=stk[-1]\n",
    "                stk.append(i)\n",
    "            res=sum(heights[i]*(suf[i]-i)*(i-pre[i]) for i in range(len(heights)))\n",
    "            print(heights,pre[i],suf[i],res)\n",
    "            return res\n",
    "        \n",
    "        res=0\n",
    "        heights=[0]*len(mat[0])\n",
    "        for n in mat:\n",
    "            for i in range(len(n)):\n",
    "                heights[i]=heights[i]+1 if n[i] else 0\n",
    "            res+=calc(heights)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        \n",
    "        row = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    ans += col\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        pos = []\n",
    "\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        ans = 0\n",
    "        dp = [[0]*(n+1) for i in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dp[i+1][j+1] = 0\n",
    "                else:\n",
    "                    dp[i+1][j+1] = dp[i+1][j] + 1\n",
    "                \n",
    "                    w = dp[i+1][j+1]\n",
    "                    for k in range(i,-1,-1):\n",
    "                        # h = k-i+1\n",
    "                        w = min(w, dp[k+1][j+1])\n",
    "                        ans += w\n",
    "                        if w == 0:\n",
    "                            break\n",
    "                            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "还是枚举每个点作为右下角\n",
    "枚举高度，宽度的取值范围为min(l1,l2,l3,...)\n",
    "\n",
    "找特殊，如果l是递增的，直接求前缀和即可\n",
    "所以，单调栈维护递增序列，但是还要记录一下出现的位置（序号），方便维护前缀和\n",
    "'''\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        #要开n个st[]\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        #类似哨兵\n",
    "        st=[[-1] for _ in range(n)]\n",
    "        s=[0]*n  \n",
    "        left=[[0]*n for _ in range(m)]\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                if j==0:\n",
    "                    left[i][j]=x\n",
    "                    continue\n",
    "                left[i][j]=left[i][j-1]+1 if x==1 else 0\n",
    "        ans=0\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                if x==0:\n",
    "                    st[j]=[i]\n",
    "                    s[j]=0\n",
    "                    continue\n",
    "                while len(st[j])>1 and left[st[j][-1]][j]>=left[i][j]:\n",
    "                    s[j]-=left[st[j][-1]][j]*(st[j].pop()-st[j][-1])\n",
    "                \n",
    "                s[j]+=left[i][j]*(i-st[j][-1])\n",
    "                ans+=s[j]\n",
    "                st[j].append(i)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        row = [[0] * m for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = (row[i][j-1] + mat[i][j]) if mat[i][j] != 0 else 0\n",
    "        \n",
    "        for j in range(m):\n",
    "            Q = list()\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                height = 1\n",
    "                while len(Q) > 0 and Q[-1][0] > row[i][j]:\n",
    "                    total -= Q[-1][1] * (Q[-1][0] - row[i][j])\n",
    "                    height += Q[-1][1]\n",
    "                    Q.pop()\n",
    "                total += row[i][j]\n",
    "                res += total\n",
    "                Q.append((row[i][j], height))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        if not mat or not mat[0]: return 0\n",
    "        \n",
    "        rows, cols = len(mat), len(mat[0])\n",
    "        dp = [[0] * cols for _ in range(rows)]  # DP 初始化\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if mat[i][j]:\n",
    "                    dp[i][j] = ((dp[i][j-1] + 1) if j > 0 else 1)\n",
    "                    mmin = float('inf')\n",
    "                    for k in range(i, -1, -1):  # 从i开始遍历,到0结束, 计算能组成的矩阵个数\n",
    "                        mmin = min(mmin, dp[k][j])\n",
    "                        ans += mmin\n",
    "                        \n",
    "                        # 提前结束循环\n",
    "                        if mmin == 0: \n",
    "                            break\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        \n",
    "        row = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    ans += col\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[m-1][j] = 1 if mat[m-1][j] == 1 else 0\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if mat[i][j] == 1:\n",
    "                    dp[i][j] = dp[i+1][j] + 1\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    ans += dp[i][j]\n",
    "                min_val = dp[i][j]\n",
    "                for h in range(j+1, n):\n",
    "                    if mat[i][h] == 0:\n",
    "                        break\n",
    "                    if dp[i][h] < min_val:\n",
    "                        min_val = dp[i][h]\n",
    "                    ans += min_val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        \n",
    "        row = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    row[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                col = row[i][j]\n",
    "                for k in range(i, -1, -1):\n",
    "                    col = min(col, row[k][j])\n",
    "                    if col == 0:\n",
    "                        break\n",
    "                    ans += col\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        # h[i][j] 代表格子 i,j 向上延伸的 '高度'\n",
    "        m,n=len(mat), len(mat[0])\n",
    "        h=[]\n",
    "        for i in range(m):\n",
    "            h.append([0]*n)\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    h[i][j]=0\n",
    "                else:\n",
    "                    h[i][j] = (h[i-1][j]+1) if i>0 else 1\n",
    "        \n",
    "        hp = [[-1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            st = []\n",
    "            for j,c in enumerate(h[i]):\n",
    "                while st and h[i][st[-1]]>=c:\n",
    "                    st.pop()\n",
    "                if not st:\n",
    "                    hp[i][j]=-1\n",
    "                else:\n",
    "                    hp[i][j]=st[-1]\n",
    "                st.append(j)\n",
    "        ans = 0\n",
    "        # 123321\n",
    "        for i in range(m):\n",
    "            dp = [0]*n\n",
    "            for j in range(n):\n",
    "                p = hp[i][j]\n",
    "                dp[j]=h[i][j]*(j-p)+(dp[p] if p>=0 else 0)\n",
    "                ans += dp[j]\n",
    "            # print(dp, hp[i], h[i])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 利用二维前缀和-超时\n",
    "# class twoDimensionPrefixSum:\n",
    "#     def __init__(self,matrix):\n",
    "#         m=len(matrix)\n",
    "#         n=len(matrix[0])\n",
    "#         self.prefixSum=[[0]*(n+1) for _ in range(m+1)]\n",
    "#         for i in range(1,m+1):\n",
    "#             for j in range(1,n+1):\n",
    "#                 self.prefixSum[i][j]=self.prefixSum[i][j-1]+self.prefixSum[i-1][j]-self.prefixSum[i-1][j-1]+matrix[i-1][j-1]\n",
    "#     def query(self,leftUp,rightDown):\n",
    "#         return self.prefixSum[rightDown[0]+1][rightDown[1]+1]-self.prefixSum[rightDown[0]+1][leftUp[1]]-self.prefixSum[leftUp[0]][rightDown[1]+1]+self.prefixSum[leftUp[0]][leftUp[1]]\n",
    "\n",
    "# class Solution:\n",
    "#     def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "#         prefixSum=twoDimensionPrefixSum(mat)\n",
    "#         m=len(mat)\n",
    "#         n=len(mat[0])\n",
    "#         ans=0\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 if mat[i][j]==0:\n",
    "#                     continue\n",
    "#                 for p in range(m):\n",
    "#                     if p<i:\n",
    "#                         continue\n",
    "#                     for q in range(n):\n",
    "#                         if q<j:\n",
    "#                             continue\n",
    "#                         if mat[p][q]==0:\n",
    "#                             continue\n",
    "#                         if prefixSum.query([i,j],[p,q])==(p-i+1)*(q-j+1):\n",
    "#                             ans+=1\n",
    "#         return ans\n",
    "\n",
    "# # 动态规划-超时\n",
    "# class Solution:\n",
    "#     def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "#         m=len(mat)\n",
    "#         n=len(mat[0])\n",
    "#         ans=0\n",
    "#         # dp[i][j][p][q]表示以[i,j]为左上角，[p,q]右下角的子矩阵，是否是全一\n",
    "#         dp=[[[[False]*n for _ in range(m)] for _ in range(n)] for _ in range(m)]\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 for p in range(i,m):\n",
    "#                     for q in range(j,n):\n",
    "#                         if i==p and j==q:\n",
    "#                             dp[i][j][p][q]=(mat[i][j]==1)\n",
    "#                             if dp[i][j][p][q]:\n",
    "#                                 ans+=1\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 for p in range(i,m):\n",
    "#                     if p<i:\n",
    "#                         continue\n",
    "#                     for q in range(j,n):\n",
    "#                         if q<j:\n",
    "#                             continue\n",
    "#                         if i==p and j==q:\n",
    "#                             continue\n",
    "#                         if i==p:\n",
    "#                             dp[i][j][p][q]=dp[i][j][p][q-1]&(mat[p][q]==1)\n",
    "#                         elif j==q:\n",
    "#                             dp[i][j][p][q]=dp[i][j][p-1][q]&(mat[p][q]==1)\n",
    "#                         else:\n",
    "#                             dp[i][j][p][q]=dp[i][j][p][q-1]&dp[i][j][p-1][q]&(mat[p][q]==1)\n",
    "#                         if dp[i][j][p][q]:\n",
    "#                             ans+=1\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        left=[[0]*(n+1) for _ in range(m+1)]\n",
    "        up=[[0]*(n+1) for _ in range(m+1)]\n",
    "        ans=0\n",
    "        # 预处理，利用dp求出left和up\n",
    "        # left[i+1][j+1]表示mat[i][j]向左连续1的个数\n",
    "        # up[i+1][j+1]表示mat[i][j]向上连续1的个数\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if mat[i-1][j-1]==1:\n",
    "                    left[i][j]=left[i][j-1]+1\n",
    "                    up[i][j]=up[i-1][j]+1\n",
    "        # 遍历每个点，求出每个点作为子矩阵右下角点时，全1子矩阵的个数\n",
    "        # 求法：\n",
    "        # 对于点mat[i][j],依次向左遍历left[i][j]长度个点，所有点的min(前面一个up[i][j]最小值，up[i][j])加起来，就是\n",
    "        # mat[i][j]作为右下角的所有全一子矩阵的个数\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==1:\n",
    "                    # c用于统计作为右下角的所有全一子矩阵的个数，初始值为0\n",
    "                    c=0\n",
    "                    pre=m\n",
    "                    # 依次向左遍历left[i][j]长度个点\n",
    "                    for k in range(left[i+1][j+1]):\n",
    "                        cur=min(pre,up[i+1][j-k+1])\n",
    "                        c+=cur\n",
    "                        pre=cur\n",
    "                    ans+=c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        if not mat or not mat[0]:\n",
    "            return 0\n",
    "        n,m=len(mat),len(mat[0])\n",
    "        dp=[[0 for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]:\n",
    "                    dp[i][j]=(1+dp[i][j-1] if j>0 else 1)\n",
    "                    width=inf\n",
    "                    for k in range(i,-1,-1):\n",
    "                        width=min(width,dp[k][j])\n",
    "                        ans+=width\n",
    "                        if width==0:\n",
    "                            break\n",
    "        print(dp)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n, ans = len(mat), len(mat[0]), 0\n",
    "        s = [[0 for i in range(n + 1)] for i in range(m + 1)]\n",
    "\n",
    "        def check(x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "            temp = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]\n",
    "            return temp == (x2 - x1 + 1) * (y2 - y1 + 1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s[i+1][j+1] = s[i][j+1] + s[i+1][j] + mat[i][j] - s[i][j]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] != 1:\n",
    "                    continue\n",
    "                for k in range(j, n):\n",
    "                    if mat[i][k] != 1:\n",
    "                        break\n",
    "                    # 二分\n",
    "                    left, right = i, m - 1\n",
    "                    while left < right:\n",
    "                        mid = (left + right + 1) >> 1\n",
    "                        if check(i, j, mid, k):\n",
    "                            left = mid\n",
    "                        else:\n",
    "                            right = mid - 1\n",
    "                    ans += left - i + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubmat(self, mat: List[List[int]]) -> int:\n",
    "        m, n, ans = len(mat), len(mat[0]), 0\n",
    "        s = [[0 for i in range(n + 1)] for i in range(m + 1)]\n",
    "\n",
    "        def check(x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "            temp = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]\n",
    "            return temp == (x2 - x1 + 1) * (y2 - y1 + 1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s[i+1][j+1] = s[i][j+1] + s[i+1][j] + mat[i][j] - s[i][j]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] != 1:\n",
    "                    continue\n",
    "                for k in range(j, n):\n",
    "                    if mat[i][k] != 1:\n",
    "                        break\n",
    "                    left, right = i, m - 1\n",
    "                    while left < right:\n",
    "                        mid = (left + right + 1) >> 1\n",
    "                        if check(i, j, mid, k):\n",
    "                            left = mid\n",
    "                        else:\n",
    "                            right = mid - 1\n",
    "                    ans += left - i + 1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
